The invention relates to distributing computations in a parallel processing environment.
FPGAs (Field Programmable Gate Arrays) and ASICs (Application Specific Integrated Circuits) are two exemplary approaches for implementing customized logic circuits. An ASIC is designed for a specific application. The cost of building an ASIC includes the cost of verification, the cost of physical design and timing closure, and the NRE (non-recurring costs) of creating mask sets and fabricating the ICs. Due to the increasing costs of building an ASIC, FPGAs became increasingly popular in the late 1990's. Unlike an ASIC, an FPGA is reprogrammable in that it can be reconfigured for each application. Similarly, as protocols change, an FPGA design can be changed even after the design has been shipped to customers, much like software can be updated. However, FPGAs are typically more expensive, often costing 10 to 100 times more than an ASIC. FPGAs are typically power hungry and their performance can be 10 to 20 times worse than that of an ASIC.
The MIT Raw integrated circuit design provides reconfigurability of an FPGA along with the performance and capability of an ASIC. The MIT Raw design is an example of a tiled integrated circuit (IC) providing a computational substrate as described, for example, in “Baring It All to Software: RAW Machines” IEEE Computer, September 1997, pp. 86-93. Techniques for compiling instructions and scheduling communication in Raw integrated circuits are described, for example, in “Space-Time Scheduling of Instruction-Level Parallelism on a Raw Machine,” Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VIII), San Jose, Calif., Oct. 4-7, 1998, incorporated herein by reference.